#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'

int n, w;
int a[46];
int b[1 << 23], num;
int ans;
void dfs(int s, int sum) {
  if (s == n / 2) {
    b[num++] = sum;
    return;
  }
  dfs(s + 1, sum);
  if (a[s] <= w - sum) dfs(s + 1, sum + a[s]);
}
void dfs2(int s, int sum) {
  if (s == n) {
    ans = max(ans, *(upper_bound(b, b + num, w - sum) - 1) + sum);
    return;
  }
  dfs2(s + 1, sum);
  if (a[s] <= w - sum) dfs2(s + 1, sum + a[s]);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> w >> n;
  rep(i, 0, n - 1) cin >> a[i];
  sort(a, a + n);
  reverse(a, a + n);
  dfs(0, 0);
  sort(b, b + num);
  num = unique(b, b + num) - b;
  dfs2(n / 2, 0);
  cout << ans;
  return 0;
}